public class HeapSort {

    /**
     * 创建最大堆
     * 
     * @param array
     */
    public static void buildMaxHeap(int[] array) {
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            heapSort(array, i, array.length);
        }
    }

    /**
     * 堆排序
     * @param array
     * @param idx
     * @param len
     */
    public static void heapSort(int[] array, int idx, int len) {
        if (len <= 1)
            return;
        int maxIdx = idx;
        if (idx * 2 + 1 < len && array[idx * 2 + 1] > array[maxIdx])
            maxIdx = idx * 2 + 1;// 左子节点与根节点比较
        if (idx * 2 + 2 < len && array[idx * 2 + 2] > array[maxIdx])
            maxIdx = idx * 2 + 2;// 右子节点与上一次最大点比较

        if (maxIdx != idx) {
            swap(array, maxIdx, idx);
            heapSort(array, maxIdx, len);//对产生影响的子节点为根节点的树进行排序
        }
    }

    public static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    public static void print(int[] array) {
        for (int i : array) {
            System.out.print(i + ",");
        }
        System.out.println();
        System.out.println("*********************");
    }

    public static void main(String[] args) {
        // int[] array = {2,9,12,3,1,8,99,7};
        // int[] array = {7,1,3,2};
        // int[] array = {1,2,3,4,5};
        int[] array = { 2, 1, 4, 0, 12, 520, 2, 9, 5, 3, 13, 14 };
        buildMaxHeap(array);

        print(array);

        int num = array.length - 1;
        while (num > 0) {
            swap(array, 0, num);//根位置最大点取出 对树重新排序
            heapSort(array, 0, num);
            num--;
            // print(array);
        }
        print(array);
    }
}